#pragma once
#include <initializer_list>
#include <memory>
#include <stdexcept>

template <class T, class A = std::allocator<T>>
class vector
{
public:
    using size_type = unsigned long;
    using value_type = T;
    using iterator = T *;
    using const_iterator = const T *;

    vector() : sz(0), elem(nullptr), space(0) {}

    explicit vector(size_type n, const T &val = T());
    vector(std::initializer_list<T> lst);
    vector(const vector &v);
    vector &operator=(const vector &v);
    vector(vector &&v) noexcept;
    vector &operator=(vector &&v) noexcept;
    ~vector() { destroy_and_deallocate(); }
    T &at(size_type i);
    const T &at(size_type i) const;
    T &operator[](size_type i) { return elem[i]; }
    const T &operator[](size_type i) const { return elem[i]; }
    T &front() { return elem[0]; }
    const T &fron() const { return elem[0]; }
    T &back() { return elem[sz - 1]; }
    const T &back() const { return elem[sz - 1]; }
    iterator begin() { return elem; }
    const_iterator begin() const { return elem; }
    iterator end() { return elem + sz; }
    const_iterator end() const { return elem + sz; }
    void reserve(size_type new_space);
    void resize(size_type new_size, const T &val = T());
    void push_back(const T &val);
    void pop_back();
    iterator insert(iterator p, const T &val);
    iterator erase(iterator p);
    void clear();
    const int size() { return sz; }

private:
    void construct(T *first, T *last, const T *from);
    void fill(T *first, T *lase, const T &val);
    void destroy(T *first, T *last);
    void destroy_and_deallocate();
    size_type sz;
    T *elem;
    size_type space;
    A alloc;
};
template <class T, class A>
void vector<T, A>::fill(T *first, T *lase, const T &val)
{
    while (first < lase)
    {
        alloc.construct(first, val);
        ++first;
    }
}

template <class T, class A>
void vector<T, A>::construct(T *first, T *last, const T *from)
{
    int i = 0;
    while (first < last)
    {
        alloc.construct(first, *from);
        first++;
        from++;
    }
}

template <class T, class A>
vector<T, A>::vector(size_type n, const T &val)
    : sz(n), elem(alloc.allocate(n)), space(n)
{
    fill(elem, elem + n, val);
}
template <class T, class A>
vector<T, A>::vector(std::initializer_list<T> lst) : sz(lst.size()), elem(alloc.allocate(lst.size())), space(lst.size())
{
    construct(elem, elem + lst.size(), lst.begin());
}
template <class T, class A>
vector<T, A>::vector(const vector &v)
    : sz(v.sz), elem(alloc.allocate(v.space)), space(v.space)
{
    construct(elem, elem + v.sz, v.elem);
}

template <class T, class A>
vector<T, A> &vector<T, A>::operator=(const vector &v)
{
    if (this == &v)
        return *this;
    if (v.sz <= space)
    {
        destroy(elem, elem + sz);
        construct(elem, elem + v.sz, v.elem);
        sz = v.sz;
        return *this;
    }
    T *p = alloc.allocate(v.sz);
    construct(p, p + v.sz, v.elem);
    destroy_and_deallocate();
    elem = p;
    space = sz = v.sz;
    return *this;
}
template <class T, class A>
vector<T, A>::vector(vector &&v) noexcept : sz(v.sz), elem(v.elem), space(v.space)
{
    v.space = v.sz = 0;
    v.elem = nullptr;
}
template <class T, class A>
vector<T, A> &vector<T, A>::operator=(vector &&v) noexcept
{
    destroy_and_deallocate();
    elem = v.elem;
    sz = v.sz;
    space = v.space;
    v.elem = nullptr;
    v.space = v.sz = 0;
    return *this;
}
template <class T, class A>
T &vector<T, A>::at(size_type i)
{
    if (i > sz)
        throw std::out_of_range("index out of range");
    return elem[i];
}
template <class T, class A>
const T &vector<T, A>::at(size_type i) const
{
    if (i > sz)
        throw std::out_of_range("index out of range");
    return elem[i];
}
template <class T, class A>
void vector<T, A>::reserve(size_type new_space)
{
    if (new_space <= space)
        return;
    T *p = alloc.allocate(new_space);
    construct(p, p + sz, elem);
    destroy_and_deallocate();
    elem = p;
    space = new_space;
}
template <class T, class A>
void vector<T, A>::resize(size_type new_size, const T &val)
{
    reserve(new_size);
    fill(elem + sz, elem + new_size, val);
    destroy(elem + new_size, elem + sz);
    sz = new_size;
}
template <class T, class A>
void vector<T, A>::push_back(const T &val)
{
    if (space == 0)
    {
        reserve(8);
    }
    else if (sz == space)
    {
        reserve(2 * space);
    }
    alloc.construct(&elem[sz], val);
    ++sz;
}
template <class T, class A>
void vector<T, A>::pop_back()
{
    alloc.destroy(elem + sz - 1);
    --sz;
}
template <class T, class A>
typename vector<T, A>::iterator vector<T, A>::insert(iterator p, const T &val)
{
    if (p == end())
    {
        push_back(val);
        return end() - 1;
    }
    int index = p - begin();
    if (sz == space)
    {
        reserve(size() == 0 ? 8 : 2 * space);
    }
    alloc.construct(elem + sz, back());
    ++sz;
    iterator pp = begin() + index;
    for (auto pos = end() - 1; pos != pp; --pp)
    {
        *pos = *(pos - 1);
    }
    *pp = val;
    return pp;
}
template <class T, class A>
typename vector<T, A>::iterator vector<T, A>::erase(iterator p)
{
    if (p == end())
        return p;
    for (auto pos = p + 1; pos != end(); ++pos)
        *(pos - 1) = *pos;        // copy element one position to the left
    alloc.destroy(&*(end() - 1)); // destroy surplus copy of last element
    --sz;
    return p;
}

// remove all elements
template <class T, class A>
void vector<T, A>::clear()
{
    destroy(elem, elem + sz);
    sz = 0;
}
// destroy elements in [first, last)
template <class T, class A>
void vector<T, A>::destroy(T *first, T *last)
{
    for (; first < last; ++first)
        alloc.destroy(first);
}

template <class T, class A>
void vector<T, A>::destroy_and_deallocate()
{
    destroy(elem, elem + sz);
    alloc.deallocate(elem, space);
}